package com.czk.hashTable;

import java.util.Random;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/7/4 22:29
 */
public class HashtableDemo {
    public static void main(String[] args) {
        HashTable table = new HashTable(7);
        for (int i = 0; i < 20; i++) {
             int id = new Random().nextInt(100);
            String name = "czk" + i;
            Employee employee = new Employee(id, name);
            table.add(employee);
        }
        table.list();
        table.getEmployeeById(10);
        System.out.println(123);
    }
}

/**
 * hashtable用于管理多条链表
 */
class HashTable {
    // 链表数组
    private EmLinkedList[] emLinkedListArray;
    // 指定size
    private int size;

    // 构造方法、传入数组长度
    public HashTable(int size) {
        this.size = size;
        // 创建数组
        emLinkedListArray = new EmLinkedList[size];
        // 不要忘记初始化链表
        for (int i = 0; i < size; i++) {
            emLinkedListArray[i] = new EmLinkedList();
        }
    }

    // 添加雇员
    public void add(Employee employee) {
        // 根据员工id,判断应该放在哪个链表
        int hash = this.hash(employee.id);
        // 添加到对应的链表中
        emLinkedListArray[hash].add(employee);
    }

    // 遍历所有的链表
    public void list() {
        for (EmLinkedList emLinkedList : emLinkedListArray) {
            emLinkedList.list();
        }
    }

    // 编写一个散列函数
    // 这里使用简单的取模法
    public int hash(int id) {
        return id % size;
    }

    // 根据输入id查找雇员
    public Employee getEmployeeById(int id) {
        // 调用散列函数
        int hash = this.hash(id);
        EmLinkedList emLinkedList = emLinkedListArray[hash];
        Employee byId = emLinkedList.getById(id);
        System.out.println(byId.id + "  " + byId.name);
        return byId;
    }
}

/**
 * 雇员类
 */
class Employee {
    // id
    public int id;
    // 名字
    public String name;
    // 下一位
    public Employee next; //此时默认为空

    public Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

class EmLinkedList {
    // 头指针，指向第一个雇员，因此这个链表没有头结点
    private Employee head;//默认为空

    // 添加雇员
    public void add(Employee employee) {
        // 假定添加雇员时，id自增，添加到当前的链表之后
        // 如果是添加第一个雇员
        if (head == null) {
            head = employee;
            return;
        }
        // 如果不是第一个雇员，则使用辅助指针添加到最后
        Employee current = head;
        while (true) {
            if (current.next == null) {
                current.next = employee;
                break;
            } else {
                // 指针后移
                current = current.next;
            }
        }
    }

    /**
     * 遍历链表
     */
    public void list() {
        if (head == null) {
            System.out.println("当前链表为空");
            return;
        }
        Employee current = head;
        while (true) {
            if (current != null) {
                System.out.println(current.id + "  " + current.name);
                current = current.next;
            } else {
                break;
            }
        }
    }

    // 根据id查找员工
    public Employee getById(int id) {
        //
        if (head == null) {
            System.out.println("当前链表为空");
            return null;
        }
        Employee current = head;
        while (true && current != null) {
            if (current.id == id) {
                return current;
            } else {
                current = current.next;
            }
        }
        return null;
    }
}
